package xyf.p05.heap_trie;

import java.util.*;

/**
 * ClassName: P0347_TopK
 * Description:
 * Author: xyf
 * Date: 9/23/22 9:02 PM
 * Version: 1.0
 **/
public class P0347_TopK
{
    public int[] topKFrequent(int[] nums, int k)
    {
        HashMap<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++)
        {
            Integer cnt = numMap.getOrDefault(nums[i], 0);
            numMap.put(nums[i], cnt + 1);
        }

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(new Comparator<Integer>()
        {
            @Override
            public int compare(Integer o1, Integer o2)
            {
                int gap = numMap.getOrDefault(o1, 0) - numMap.getOrDefault(o2, 0);
                if (gap == 0)
                {
                    return o1 - o2;
                }
                else
                {
                    return gap;
                }
            }
        });

        for (Map.Entry<Integer, Integer> entry : numMap.entrySet())
        {
            if (priorityQueue.size() < k)
            {
                priorityQueue.offer(entry.getKey());
            }
            else
            {
                if (entry.getValue() > numMap.getOrDefault(priorityQueue.peek(), 0))
                {
                    priorityQueue.poll();
                    priorityQueue.offer(entry.getKey());
                }
            }
        }

        return priorityQueue.stream().mapToInt(Integer::intValue).toArray();
    }
}